package day05;

import java.util.Arrays;

public class HeapSort {

        private static String[] sort1=new String[]{"S","O","R","T","E","X","A","M","P","L", "E"};
        private static String[] sort=new String[]{"A","O","C","T","K","X","A","M","P","Z", "E"};
        public static void main(String[] args){
            buildMaxHeap(sort);
            heapSort(sort);
            System.out.println(Arrays.toString(sort));
        }

        /**
         * 初始化构建堆
         * @param data
         */
        private static void buildMaxHeap(String[] data){
            //根据最后一个元素获取，开始调整的位置
            int startIndex=getParentIndex(data.length-1);//4
            //反复进行调整
            for(int i=startIndex;i>=0;i--){
                maxHeap(data,data.length,i);
            }
        }

        /**
         * 此调整为从上到下调整，直到节点超出范围,大根堆
         * @param data
         * @param heapSize
         * @param index
         */
        private static void maxHeap(String[] data,int heapSize,int index){//4
            //取得当前节点的左右节点，当前节点为index
            int left=getChildLeftIndex(index);//9
            int right=getChildRightIndex(index);//10
            //对左右节点和当前节点进行比较
            int largest=index;
            if(left<heapSize&&data[index].compareTo(data[left])<0){
                largest=left;
            }
            if(right<heapSize&&data[largest].compareTo(data[right])<0){
                largest=right;
            }
            //交换位置
            if(largest!=index){
                String temp=data[index];
                data[index]=data[largest];
                data[largest]=temp;
                //当Index=0的时候,最大值就放在了根节点
                maxHeap(data,heapSize,largest);
            }
        }

        /**
         * 排序操作
         * @param data
         * //
         */
        private static void heapSort(String[] data){
            //每次循环都能取到一个最大值，该值为根节点的值,并且把他存放在末尾,把另一个数放在根节点,执行
            //maxHeap方法,但是不比较下标已经存放的数,只比较没存放的,
            //比较完毕,又得到一个第二大的数,继续存在当前的i
            for(int i=data.length-1;i>0;i--){
                String temp=data[0];
                data[0]=data[i];
                data[i]=temp;
                //每次调整都是从根节点开始i不断减小，保证前一次最大节点不会参与到调整堆
                maxHeap(data,i,0);
            }
        }

        /**
         * 获取父节点的位置
         * @param current
         * @return
         */
        private static int getParentIndex(int current){
            //(N-1)/2
            return(current-1)>>1;
        }

        /**
         * 获得左子节点的位置
         * @param current
         * @return
         */
        private static int getChildLeftIndex(int current){
            return(current<<1)+1;
        }

        /**
         * 获得右子节点的位置
         * @param current
         * @return
         */
        private static int getChildRightIndex(int current){
            return(current<<1)+2;
        }


}
